/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

/**
 * @author : sunzb
 * @date: 2019/5/16
 */
public class _30_70_ClimbingStairs {

    public int climbStairs(int n) {
        // 状态 dp[n] 几种方式达到n
        // 转移方程 dp[n] = opt[n - 1] + opt[n - 2]
        if (n < 3) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }

    public static void main(String[] args) {

    }
}
